// https://leetcode.cn/problems/jC7MId/submissions/498200999/
import TreeNode from "./TreeNode";



function maxPathSum(root: TreeNode | null): number {

    let maxSum: number = -Infinity;
    // 定义内部函数进行递归操作
    function dfs(node: TreeNode | null): number {
        if (!node) return 0;
        
        // 左子树和右子树所能提供的最大值
        const leftSum = Math.max(dfs(node.left),0);
        const rightSum = Math.max(dfs(node.right),0);

        // 当前节点中能获得的最大值，包括父节点
        const pathSum = node.val + leftSum + rightSum;
        maxSum = Math.max(maxSum,pathSum);

        // 返回当前节点能给父节点提供的最大值，不把左右都加上的原因是因为，不能重复经过一个节点，因为这里是给父节点提供的
        return node.val +  Math.max(leftSum, rightSum);
    }

    dfs(root)
    return maxSum
};

export {}